package com.zyk.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/4/30 15:12
 */
public class M1619 {

    // 不想, 先来一遍DFS
    public static int[] pondSizes(int[][] land) {
        int R = land.length, C = land[0].length;
        List<Integer> res = new ArrayList<>();

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (land[r][c] == 0) {
                    res.add(dfs(land, r, c, R, C));
                }
            }
        }
        int[] ans = res.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(ans);
        return ans;
    }

    private static int dfs(int[][] land, int r, int c, int R, int C) {
        if (r == R || c == C || r < 0 || c < 0) return 0;
        if (land[r][c] != 0) return 0;
        land[r][c] = 1; // 换成别的, 用过了
        // 全试吧
        int area = 1
                + dfs(land, r, c - 1, R, C)           // 左
                + dfs(land, r + 1, c, R, C)           // 下
                + dfs(land, r - 1, c, R, C)           // 上
                + dfs(land, r, c + 1, R, C)           // 右
                + dfs(land, r - 1, c - 1, R, C)    // 左上
                + dfs(land, r + 1, c - 1, R, C)    // 左下
                + dfs(land, r - 1, c + 1, R, C)    // 右上
                + dfs(land, r + 1, c + 1, R, C);   // 右下
        return area;
    }

    // BFS, 同理也是从每个角开始一次. 是0加入队列, 思路一样.实现略

    // 并查集实现
    // 并查集实现
    public static int[] pondSizes2(int[][] land) {
        int R = land.length, C = land[0].length;
        List<Integer> res = new ArrayList<>();
        int area = R * C;
        UnionFind uf = new UnionFind(area);

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (land[r][c] == 0) {
                    if (c - 1 >= 0 && land[r][c - 1] == 0) uf.union(index(r, c, C), index(r, c - 1, C));
                    if (r + 1 < R && land[r + 1][c] == 0) uf.union(index(r, c, C), index(r + 1, c, C));
                    if (r - 1 >= 0 && land[r - 1][c] == 0) uf.union(index(r, c, C), index(r - 1, c, C));
                    if (c+1 < C && land[r][c + 1] == 0) uf.union(index(r, c, C), index(r, c + 1, C));
                    if (c - 1 >= 0 && r - 1 >= 0 && land[r - 1][c - 1] == 0)
                        uf.union(index(r, c, C), index(r - 1, c - 1, C));
                    if (c - 1 >= 0 && r + 1 < R && land[r + 1][c - 1] == 0)
                        uf.union(index(r, c, C), index(r + 1, c - 1, C));
                    if (c+1 < C && r - 1 >= 0 && land[r - 1][c + 1] == 0)
                        uf.union(index(r, c, C), index(r - 1, c + 1, C));
                    if (c+1 < C && r + 1 < R && land[r + 1][c + 1] == 0)
                        uf.union(index(r, c, C), index(r + 1, c + 1, C));
                }
            }
        }
        HashSet<Integer> visited = new HashSet<>();
        int index;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (land[r][c] == 0 && !visited.contains(
                        (index = uf.findHead(index(r, c, C))) )
                        ) {
                    res.add(uf.size[index]);
                    visited.add(index);
                }
            }
        }
        int[] ans = res.stream().mapToInt(Integer::intValue).toArray();
        Arrays.sort(ans);
        return ans;
    }

    // 二维转一维
    private static int index(int r, int c, int C) {
        return r * C + c;
    }

    // 并查集
    public static class UnionFind {
        int[] parents;
        // size数组决定把谁关联到谁上边减轻移动过程
        int[] size;
        // help数组是为了加速,找父过程
        int[] help;
        int sets;

        public UnionFind(int n) {
            parents = new int[n];
            for (int i = 0; i < n; i++) {
                parents[i] = i;
            }

            size = new int[n];
            Arrays.fill(size, 1);

            help = new int[n];
            sets = n;
        }

        /**
         * 寻找他所在的集的头节点
         */
        private int findHead(int i) {
            // 重头戏, 查找父的过程要快. 在查找的时候把他们都直接指向头节点. 这样后序查找就能很快地找到
            int helpIndex = 0;
            while (parents[i] != i) {
                help[helpIndex++] = i;  // 记录寻找一路过程中的元素
                i = parents[i];
            }
            // 最后i来到了头元素, 把这里一路的元素直接指向i
            while (helpIndex > 0) {
                parents[help[--helpIndex]] = i;
            }
            return i;       // 返回这个方法要找的东西
        }

        /**
         * 是否同一组
         */
        public boolean isSameSet(int a, int b) {
            return findHead(a) == findHead(b);
        }


        public void union(int i, int j) {
            // 找到他俩的头
            int iHead = findHead(i);
            int jHead = findHead(j);
            if (iHead != jHead) {
                // 不在一起开始合并, 看谁的元素少, 谁移动
                if (size[iHead] >= size[jHead]) {
                    // i的大, 移动j所在的并查集
                    parents[jHead] = iHead;
                    size[iHead] += size[jHead];
                    size[jHead] = 0;
                } else {
                    // j的大, 移动i所在的并查集
                    parents[iHead] = jHead;
                    size[jHead] += size[iHead];
                    size[iHead] = 0;
                }
                sets--; // 移动完了,别忘记把集的数量-1;
            }
        }

        /**
         * 内部现在有多少个集
         */
        public int sets() {
            return sets;
        }
    }

    // for test
    public static void main(String[] args) {

        /*int[][] land = {
                {0, 0},
                {3, 0}
        };
        int[][] land2 = {
                {0, 0},
                {3, 0}
        };
        System.out.println(Arrays.toString(pondSizes(land)));
        System.out.println(Arrays.toString(pondSizes2(land2)));*/

        int times = 10000;
        int maxLen = 50;
        System.out.println("test begin!");
        for (int i = 0; i < times; i++) {
            int[][] land = generateLand(maxLen);
            int[][] land2 = copyLand(land);
            int[] ans1 = pondSizes(land);
            int[] ans2 = pondSizes2(land2);
            if (!Arrays.equals(ans1, ans2)) {
                System.out.println("OOPS");
                for (int[] arr : land2) {
                    System.out.println(Arrays.toString(arr));
                }
                System.out.println("DFS: ");
                System.out.println(Arrays.toString(ans1));
                System.out.println("并查集: ");
                System.out.println(Arrays.toString(ans2));
                break;
            }
        }
        System.out.println("test end!");
    }

    public static int[][] generateLand(int maxLen) {
        maxLen = (int) (Math.random() * maxLen) + 1;
        int[][] res = new int[maxLen][maxLen];
        for (int r = 0; r < maxLen; r++) {
            for (int c = 0; c < maxLen; c++) {
                res[r][c] = Math.random() < 0.2 ? 0 : (int) (Math.random() * 100);
            }
        }
        return res;
    }

    public static int[][] copyLand(int[][] land) {
        int N = land.length;
        int[][] newLand = new int[N][N];
        for (int r = 0; r < N; r++) {
            System.arraycopy(land[r], 0, newLand[r], 0, N);
        }
        return newLand;
    }

}
